# -*- coding: utf-8 -*-

"""剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
说明：
    0 <= n <= 10^5

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101"""

class Solution:
    """1位满1、2位满1、3位满1、4位满1......的时候，前后都是翻倍关系，且2位满1到3位满1之间都是高位进1，追加2位满1的情形
    1        2**1-1  1
    11       2**2-1  3
    111      2**3-1  7
    1111     2**4-1  15
    
    0
    1
    --进位翻倍 指数1--
    10
    11
    --进位翻倍 指数2--
    100
    101
    110
    111
    --进位翻倍 指数3--
    1000
    1001
    1010
    1011
    1100
    1101
    1110
    1111

    GREAT!!! 执行时间超过99.46%的提交
    """
    fulls = (1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071)
    init = [0, 1]

    def select_max_full_num_exp(self, n):
        def binsearch(imin, imax):
            if imax-imin == 1:
                return imin

            imid = (imin+imax)//2
            if self.fulls[imid] < n:
                imin, imax = imid, imax
            elif self.fulls[imid] > n:
                imin, imax = imin, imid
            else:
                imin, imax = imid, imid+1
            return binsearch(imin, imax)

        imin, imax = 0, len(self.fulls)-1
        i = binsearch(imin, imax)
        exp = i+1
        return (exp, self.fulls[i])

    def countBits(self, n: int):
        if n == 0:
            return [0]
        
        if n == 1:
            return self.init

        exp, pren = self.select_max_full_num_exp(n)

        def double(exp):
            if exp == 1:
                return [0, 1]
            rs = double(exp-1)
            rs += [c+1 for c in rs]
            return rs
        
        precb = double(exp)
        precb += [c+1 for c in precb[0:n-pren]]
        return precb


if __name__ == '__main__':
    for i in range(1, 15+1):
        print('i:%s, n:%s' % (i, bin(i)))
    so = Solution()
    rs = so.countBits(112)
    print(rs)

